class Solution {//leetcode912——排序数组
private:
    void _swap(int&lhs,int&rhs){
        int tmp=rhs;
        rhs=lhs;
        lhs=tmp;
    }
    void q_sort(vector<int>&nums,int begin,int end){//快速排序[begin,end]
        if(begin>=end) return;
        //找到基准元素key
        int left=begin-1,right=end+1,i=begin;
        int keyi=rand()%(end-begin+1)+begin;
        int key=nums[keyi];
        while(i<right){
            if(nums[i]<key) _swap(nums[++left],nums[i++]);
            else if(nums[i]==key) i++;
            else _swap(nums[--right],nums[i]);
        }
        q_sort(nums,begin,left);
        q_sort(nums,right,end);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned int)time(nullptr));
        q_sort(nums,0,nums.size()-1);
        return nums;
    }
};